package com.mhg.collection.theList;

import java.util.Scanner;

public class Main1 {

    public static int sum=0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组：");
        String str = sc.nextLine();
        String[] arr = str.split(" ");
        Integer[] a = new Integer[arr.length];
        for (int i=0;i<a.length;i++){
            a[i] = Integer.parseInt(arr[i]);
        }
        System.out.println("请输入k的值：");
        int k = sc.nextInt();
        quick_sort(a,0,k);
        System.out.println(sum);
    }

    public static void quick_sort(Integer a[], int l, int r) {
        if (l >= r) return;
        int i = l, j = r, x = a[l];
        while (i < j) {
            while (i < j && x <= a[j]) j--;
            if(a[i]!=a[j]){
                a[i]=a[j];
                sum++;
                i++;
            }
            while (i < j && x >= a[i]) i++;
            if(a[j]!=a[i]){
                a[j]=a[i];
                sum++;
                j--;
            }
        }
        a[i] = x;
        quick_sort(a, l, i - 1);
        quick_sort(a, i + 1, r);
    }
}
